package edu.dayu.demo4;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。
 * 输入：s = "ADOBECODEBANC", t = "ABC"
 * 输出："BANC"
 * 解释：最短子字符串 "BANC" 包含了字符串 t 的所有字符 'A'、'B'、'C'
 *
 * 思路：子字符串，连续的。 包含 t 字符串的所有字符，重复的也要包括。
 *      滑动窗口，首先从 0 开始滑，滑到包括 t 字符串，然后从 左边开始减。减到不包括，记录一下，然后继续向右。
 *      那么问题转化为，怎么快速判断是否包含这个 字符串？
 *      把 包含 转换为，一个 count 记录有多少符合要求，这样就只要判断数组 里的数字是否相等。
 */
public class 含有所有字符的最短字符串 {
    public static void main(String[] args) {
        String s = "ADOBECODEBANC", t = "ABC";
        System.out.println(minWindow(s,t));
    }

    public static String minWindow(String s, String t) {
        // 因为 asci 码值
        int[] a = new int[58],b = new int[58];
        int left =0,right = 0,count =0;
        String res = "";
        for (int i = 0; i < t.length(); i++) {
            b[t.charAt(i)-'A']++;
        }

        while (right<s.length()){
            a[s.charAt(right)-'A']++;

            // 因为 初始 a 数组为空 ， 所以用 《= 来比较，a 存在 b 不在就不符合条件，只有 a 存在就 count ++；
            if (a[s.charAt(right)-'A'] <= b[s.charAt(right)-'A'])count++;

            // 这个条件 表示 当 a 中的 不属于 b 的，或者 比 b 多，那么肯定不是最短的，左指针移动；
            while (left<=right && a[s.charAt(left)-'A'] > b[s.charAt(left)-'A']){
                a[s.charAt(left)-'A']--;
                left++;
            }

            if(count == t.length() && (res.isEmpty() || res.length() > right - left + 1))
                res = s.substring(left, right + 1);

            right++;
        }
        return  res;
    }
}
